// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-08 11:05
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class PlatesBetweenCandlesUpdate {

    /**
     * 使用一次遍历实现 -> Hash搜索 -> 时间复杂度O(n)
     *
     * @param s       给定字符串
     * @param queries 区间蜡烛
     * @return 结果
     */
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = queries.length, m = s.length();
        int[] ans = new int[n];
        List<int[]> region = new ArrayList<>();
        List<Integer> num = new ArrayList<>();
        int pre = 0, p = 0, count = 0, k = 0;
        while (s.charAt(p) != '|') {
            p++;
        }
        pre = p;
        p++;
        while (p < m) {
            if (s.charAt(p) == '|') {
                region.add(new int[]{pre, p});
                num.add(count);
                count = 0;
                pre = p;
            }
            if (s.charAt(p) == '*') {
                ++count;
            }
            ++p;
        }
        for (int[] query : queries) {
            int start = query[0], end = query[1], tmp = 0;
            for (int i = 0; i < region.size(); i++) {
                if (region.get(i)[0] >= start && region.get(i)[1] <= end) {
                    // 当前遍历的区间是问题区间的子区间
                    tmp += num.get(i);
                }
                ans[k] = tmp;
                if (region.get(i)[1] >= end) {
                    ++k;
                    break;
                }
            }
        }
        return ans;
    }
}
